package cn.myworld.algorithm.sort;

import cn.myworld.algorithm.common.BaseSort;

/**
 * 快速排序
 */
public class Quick extends BaseSort {

    public static void sort(Comparable[] a) {
        int lo = 0, hi = a.length - 1;
        sort(a, lo, hi);
    }

    /**
     * 对数组a中从lo到hi进行排序
     * @param a
     * @param lo
     * @param hi
     */
    public static void sort(Comparable[] a, int lo, int hi) {
        // 安全性校验
        if (hi <= lo) {
            return;
        }
        // 需要对数组中lo索引到hi索引处的元素进行分组（左子组和右子组）
        int partition = partition(a, lo, hi); // 分界值位置变化后的索引

        // 让左子组有序
        sort(a, lo, partition - 1);

        // 让右子组有序
        sort(a, partition + 1, hi);
    }

    /**
     * 对数组a中从索引lo到索引hi之间的元素进行分组，并返回分组界限对应的索引
     * @param a
     * @param lo
     * @param hi
     * @return 分组界限对应的索引
     */
    public static int partition(Comparable[] a, int lo, int hi) {
        // 确定分界值
        Comparable key = a[lo];

        // 确定两个指针，分别指向待切元素的最小索引处和最大索引处的下一个位置
        int left = lo, right = hi + 1;

        // 切分
        while (true) {
            // 先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止
            while (less(key, a[--right])) {
                if (right == lo) {
                    break;
                }
            }

            // 再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止
            while (less(a[++left], key)) {
                if (left == hi) {
                    break;
                }
            }

            // 判断left>=right，如果是，则证明扫描完毕，结束循环，如果不是，则交换元素
            if (left >= right) {
                break;
            } else {
                exch(a, left, right);
            }
        }
        // 交换分界值
        exch(a, lo, right);

        return right;
    }

}
